/**
 * Created with IntelliJ IDEA.
 * Description: 对快速排序的总结
 */
public class QuickSort {
    public static void quickSort(int[] array){
        // write code  here
        quickSortChild(array,0,array.length - 1);
    }

    private static void quickSortChild1(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        int index = partition(array,start,end);
        quickSortChild1(array,start,index - 1);
        quickSortChild1(array,index + 1,end);
    }

    //对 quickSortChild 方法优化
    private static void quickSortChild(int[] array,int start,int end) {
        if(end - start < 10) {
            insertSort(array);
            return;
        }
        int index = partition(array,start,end);
        quickSortChild(array,start,index - 1);
        quickSortChild(array,index + 1,end);
    }

    //寻找分割节点的方法
    //方法一
    private static int partition1(int[] array,int start,int end) {
        int left = start;
        int right = end;
        while(left < right) {
            while(left < right && array[right] >= array[start]) {
                right--;
            }
            while(left < right && array[left] <= array[start]) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,start,left);
        return left;
    }

    //方法二
    //比较start mid end三者的值，尽量让start的值是中间值
    private static void setMid(int[] array,int start,int end) {
        int mid = (end - start) / 2 + start;
        if(array[start] < array[end]) {
            if(array[mid] < array[end] && array[mid] > array[start]) {
                swap(array,start,mid);
            }else if(array[mid] > array[end]) {
                swap(array,start,end);
            }
        } else {
            if(array[mid] < array[end]) {
                swap(array,start,end);
            }else if(array[mid] < array[start] && array[mid] > array[end]) {
                swap(array,start,mid);
            }
        }
    }

    private static int partition(int[] array,int start,int end) {
        //尽量保证分治的二叉树是完全二叉树
        setMid(array,start,end);
        int left = start;
        int right = end;
        while(left < right) {
            while(left < right && array[right] >= array[start]) {
                right--;
            }
            while(left < right && array[left] <= array[start]) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,start,left);
        return left;
    }

    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    // 插入排序
    public static void insertSort(int[] array) {
        //write code  here
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for(; j >= 0; j--) {
                if(tmp >= array[j]) {
                    array[j + 1] = tmp;
                    break;
                }else {
                    array[j + 1] = array[j];
                }
            }
            if(j < 0) {
                array[0] = tmp;
            }
        }
    }


}
